package 题目集.倍增算法.st表;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

/**
 * https://www.luogu.com.cn/problem/P4155
 */
public class Ch02_国旗计划 {

    static int maxN = (int) (2 * 1e5 + 10);
    static int maxM = (int) (1e9 + 10);
    static int n, m;
    static int power;   //倍增的最大次数

    public static void main(String[] args) {
        Reader sc = new Reader();
        n = sc.nextInt();
        m = sc.nextInt();
        power = (int) (Math.log(n) / Math.log(2))+1;    //从0开始所以需要额外+1
        int[][] lines = new int[n * 2][3];
        for (int i = 0; i < n; i++) {
            lines[i][0] = i;
            lines[i][1] = sc.nextInt();
            lines[i][2] = sc.nextInt();
            if (lines[i][1] > lines[i][2]) {
                lines[i][2] += m;
            }
        }
        //第二圈
        for (int i = n; i < lines.length; i++) {
            lines[i][0] = lines[i - n][0];
            lines[i][1] = lines[i - n][1] + m;
            lines[i][2] = lines[i - n][2] + m;
        }
        Arrays.sort(lines, (a, b) -> a[1] - b[1]);
        int[][] st = buildST(lines);
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            //当前点
            int now = i;
            //当前点要抵达的终点
            int over = i + n;
            //逼近over需要的步数（st表查找）
            int res = 0;
            for (int p = power-1; p >= 0; p--) {
                if (st[now][p] < over) {
                    res += 1 << p;
                    now = st[now][p];
                }
            }
            //因为仅仅是逼近，并不是覆盖，所以要+1
            ans[lines[i][0]] = res + 1;
        }
        for (int a : ans) {
            System.out.print(a + " ");
        }
    }

    /**
     * 构建st表
     */
    public static int[][] buildST(int[][] lines) {
        int[][] st = new int[lines.length][power];
        //构建st表第0层
        for (int i = 0, last = 0; i < lines.length; i++) {
            //大于2*m的点只有可能是第二圈的点，是无意义的点，所以可以让第二圈所有溢出的点都指向第二圈的终点，last < lines.length
            while (last < lines.length && lines[last][1] <= lines[i][2]) {
                last++;
            }
            st[i][0] = last - 1;
        }
        //构建st表后续层，i跳2^p步能抵达的点
        for (int p = 1; p < power; p++) {
            for (int i = 0; i < lines.length; i++) {
                st[i][p] = st[st[i][p - 1]][p - 1];
            }
        }
        return st;
    }


    static class Reader {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public Reader(Object... o) {
        }

        public static int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {}
            return (int) in.nval;
        }
    }
}
